'''
Pattern. A set of classes for expressing searchable lists of elements used in
the XCP code base.
Copyright (C) 2006-2007  Jonathan Claggett

This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 2.1 of the License, or (at your option) any
later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
details.

You should have received a copy of the GNU Lesser General Public License along
with this library; if not, write to the Free Software Foundation, Inc., 51
Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

You may contact the author a <jonathan@claggett.org>
'''

def Seq(items, min=None, max=None):
    return Pattern(items, ordered=True, min_each=1, max_each=1, min_all=min, max_all=max)

def Any(items, min=0, max=None):
    return Pattern(items, ordered=False, min_each=0, max_each=None, min_all=min, max_all=max)

def Choose(items, min=1, max=1):
    return Pattern(items, ordered=False, min_each=1, max_each=1, min_all=min, max_all=max)

def Each(items):
    return Pattern(items, ordered=False, min_each=1, max_each=1, min_all=None, max_all=None)

class Pattern(object):
    '''
    The Pattern function returns the proper kind of instantiated pattern object
    based on the parameters passed in.
    '''

    def __init__(self, items, ordered=True,
            min_each=None, max_each=None,
            min_all=None, max_all=None ):

        # Wrap any non-Pattern items within a Leaf (using str() to
        # determine the item's key).
        self.items = list(items)
        for index, item in enumerate(self.items):
            if not isinstance(item, (Pattern, Leaf)):
                self.items[index] = Leaf( key=str(item), value=item )

        # ordered or not
        self.ordered = (ordered == True)

        # Define and normalize the range contraints.
        if min_each == None or min_each < 0:
            min_each = 0
        if max_each != None:
            if max_each < 1:
                max_each = 1
            if min_each > max_each:
                min_each = max_each
            if max_all == None or max_all > len(items) * max_each:
                max_all = len(items) * max_each
        if min_all != None and min_all < 0:
            min_all = 0
        if min_all == None and min_each == 0:
            min_all = 0
        if max_all != None:
            if max_all < 1:
                max_all = 1
            if min_all > max_all:
                min_all = max_all

        self.min_each = min_each
        self.max_each = max_each
        self.min_all = min_all
        self.max_all = max_all

        # Define the initial_path.
        if self.ordered:
            if self.min_each > 0 and self.min_all == None:
                path = PathOrderedEachRequired
            elif self.min_each == 1 and self.max_each == 1:
                path = PathOrderedSimple
            else:
                path = PathOrdered
        else:
            if self.min_all == None:
                path = PathUnorderedEachRequired
            elif self.min_each == 0 and self.max_each == None:
                if self.min_all == 0 and self.max_all == None:
                    path = PathAny
                else:
                    path = PathUnorderedSimple
            else:
                path = PathUnordered
        self.initial_path = path(self)

        # Define keys and has_keys methods.
        if self.ordered and self.min_each > 0:
            self.has_key = self.items[0].has_key
            self.keys = self.items[0].keys
        else:
            # Build a dictionary of the keys from all childern to the child's
            # item_index in the list of items.
            self.keymap = {}
            for item_index, item in enumerate(self.items):
                for key in item.keys():
                    self.keymap.setdefault(key, []).append(item_index)

            # Use the keymap's keys() and has_key() methods as our own.
            self.keys = self.keymap.keys
            self.has_key = self.keymap.has_key

    def __str__(self):
        result = '( '
        for item in self.items:
            result += str(item) + ', '
        if self.ordered:
            ordered = 'o'
        else:
            ordered = 'u'

        min_each = str(self.min_each)

        if self.max_each == None:
            max_each = 'inf'
        else:
            max_each = str(self.max_each)

        if self.min_all == None:
            min_all = 'na'
        else:
            min_all = str(self.min_all)

        if self.max_all == None:
            max_all = 'inf'
        else:
            max_all = str(self.max_all)

        result += '[%s %s-%s %s-%s] )' % (
            ordered, min_each, max_each, min_all, max_all )
        return result

    def start(self):
        return Match(initial_path = self.initial_path)

    def match(self, iterable):
        pass
    def find(self, iterable):
        pass

class Match(object):
    def __init__(self, initial_path ):
        self.paths = [ initial_path ]
        self.happy = True
        self.value = None

    def next(self, key):
        # Create the new paths
        new_paths = []
        for path in self.paths:
            new_paths.extend( path.get_paths( key ) )
        self.paths = new_paths

        # match the key against the paths. If even one path is happy then we
        # are also happy. Our value is equal to any non-None value from
        # match.next(key).
        self.happy = False
        self.value = None
        for path in self.paths:
            happy, value = path.next(key)
            self.happy = self.happy or happy
            self.value = self.value or value

        return self.value

class Path(object):

    def __init__(self, pattern, index = -1, previous_path = None):
        self.pattern = pattern
        self.index = index

        if previous_path == None:
            self.init()
        else:
            self.init_from(previous_path)

    def init(self):
        self.match = Match( initial_path = None )

    def init_from(self, previous_path):
        self.match = self.pattern.items[self.index].start()

    def new_path(self, new_index):
        path = self.__class__(self.pattern, new_index, self)
        return path

    def get_paths(self, key):
        paths = []

        # Last time the path was used, it returned a value so use it again.
        if self.match.value != None:
            paths.append(self)

        # Another word for 'happy' might be 'pregnant'. i.e., ready to
        # create new paths.
        if self.match.happy:
            paths.extend( self.get_following_paths(key) )

        return paths

    def next(self, key):
        self.match.next( key )
        return self.get_happy() and self.match.value != None, self.match.value

    def get_following_paths(self, key):
        '''
        get_following_paths() is an implementation specific method that is expected
        to be overridden. This method should return a list of valid following paths
        given the key. Used by get_paths().
        '''
        return []

    def get_happy(self):
        '''
        get_happy() is an implementation specific method that is expected to be
        overridden. This method should return True if the current state of the
        match (as embodied by this path) is happy. Used by next().
        '''
        return True

class PathOrderedSimple(Path):
    def init(self):
        Path.init(self)
        self.sum_all = 0

    def init_from(self, previous_path):
        Path.init_from(self, previous_path)
        self.sum_all = previous_path.sum_all + 1

    def less_than_max_all(self):
        return self.pattern.max_all == None or self.sum_all < self.pattern.max_all

    def get_following_paths(self, key):
        paths = []

        if self.less_than_max_all() \
           and self.index + 1 < len(self.pattern.items) \
           and self.pattern.items[self.index + 1].has_key(key):
           paths.append( self.new_path( self.index + 1 ) )

        return paths

    def get_happy(self):
        return self.pattern.min_all <= self.sum_all - (not self.match.happy)

class PathOrdered(PathOrderedSimple):
    def init(self):
        PathOrderedSimple.init(self)
        self.sum_each = 0

    def init_from(self, previous_path):
        PathOrderedSimple.init_from(self, previous_path)
        self.sum_each = 1
        if previous_path.index == self.index:
            self.sum_each += previous_path.sum_each

    def less_than_max_each(self):
        return self.pattern.max_each == None or self.sum_each < self.pattern.max_each

    def get_following_paths(self, key):
        paths = []
        if self.less_than_max_all():

            # Start looking at the next index if this one -1 or is full.
            if self.index == -1 or not self.less_than_max_each():
                start_index = self.index + 1
                sum_each = 0
            else:
                start_index = self.index
                sum_each = self.sum_each

            for index in range(start_index, len(self.pattern.items)):
                # Stop looking for new paths when we reach a point in which it is no longer possible to satisfy the min_all constraint.
                if self.pattern.max_each != None and self.pattern.min_all != None \
                    and self.pattern.max_each * index - self.sum_all > self.pattern.max_each * len(self.pattern.items) - self.pattern.min_all:
                    break

                # if this index has the key.
                if self.pattern.items[index].has_key(key):
                    paths.append( self.new_path( index ) )

                # Stop looking for new paths if the current index has not met its minimum constraint.
                if sum_each < self.pattern.min_each:
                    break
                sum_each = 0

        return paths

class PathOrderedEachRequired(PathOrdered):

    def get_happy(self):
        return self.index == len(self.pattern.items) - 1 \
               and self.pattern.min_each <= self.sum_each - (not self.match.happy)

class PathAny(Path):

    def get_following_paths(self, key):
        return [ self.new_path( index ) for index in self.pattern.keymap[key] ]

class PathUnorderedSimple(Path):
    def init(self):
        Path.init(self)
        self.sum_all = 0

    def init_from(self, previous_path):
        Path.init_from(self, previous_path)
        self.sum_all = previous_path.sum_all + 1

    def less_than_max_all(self):
        return self.pattern.max_all == None or self.sum_all < self.pattern.max_all

    def get_following_paths(self, key):
        paths = []

        if self.less_than_max_all():
            paths = [ self.new_path( index ) for index in self.pattern.keymap.get(key, []) ]

        return paths

    def get_happy(self):
        # This path is happy if our sum_all is greater than or equal to
        # min_all. If the match below us is currently unhappy, deduct 1 from
        # our sum_all (since we can't count this path).
        return self.pattern.min_all <= self.sum_all - (not self.match.happy)

class PathUnordered(PathUnorderedSimple):
    def init(self):
        PathUnorderedSimple.init(self)
        self.sum_each = [ 0 for i in range(len(self.pattern.items)) ]

    def init_from(self, previous_path):
        PathUnorderedSimple.init_from(self, previous_path)
        self.sum_each = previous_path.sum_each[:]
        self.sum_each[self.index] += 1

    def less_than_max_each(self, index):
        return self.pattern.max_each == None or self.sum_each[index] < self.pattern.max_each

    def get_following_paths(self, key):
        paths = []

        if self.less_than_max_all():
            for index in self.pattern.keymap.get(key, []):
                if self.less_than_max_each(index):
                    paths.append( self.new_path( index ) )

        return paths

    def get_happy(self):
        return self.pattern.min_all <= self.sum_all - (not self.match.happy)

class PathUnorderedEachRequired(PathUnordered):
    def init(self):
        PathUnordered.init(self)
        self.sum_each_remaining = len(self.pattern.items)

    def init_from(self, previous_path):
        PathUnordered.init_from(self, previous_path)
        self.sum_each_remaining = previous_path.sum_each_remaining
        if self.sum_each[self.index] == self.pattern.min_each:
            self.sum_each_remaining -= 1

    def get_happy(self):
        return ( self.sum_each_remaining == 0
               and ( self.sum_each > self.pattern.min_each
                    or self.match.happy ) )

class Leaf(object):
    '''
    The Leaf class provides the bottom level of a Pattern hierarchy.
    It (trivially) implements all of the same 'public' methods as any other
    Pattern as well as the methods of Match objects as well.
    '''
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __str__(self):
        return str(self.value)

    def keys(self):
        return [self.key]

    def has_key(self, key):
        return key == self.key

    def start(self):
        return LeafMatch( pattern = self )

class LeafMatch(object):

    def __init__(self, pattern):
        self.pattern = pattern
        self.happy = True
        self.value = None

    def next(self, key):
        if self.value != None:
            self.happy = False
            self.value = None
        elif self.pattern.key == key:
            self.happy = True
            self.value = self.pattern.value
        return self.value

# Unit Testing ###################################################
if __name__ == '__main__':
    import pdb

    def check_pattern(pattern, input):
        result=''
        match = pattern.start()
        for token in input:
            match.next(token)
            result+=token
            if match.value == None:
                result += '?'
                break
            if match.happy: result += '!'
        if match.value != None and not match.happy:
            result += '...'
        return str(pattern) + ' ==> ' + result

    # Test simple, ordered patterns
    pat0 = Seq('abc')
    print check_pattern(pat0, 'acb')
    print check_pattern(pat0, 'a')
    print check_pattern(pat0, 'ab')
    print check_pattern(pat0, 'abc')
    print check_pattern(pat0, 'abca')
    print check_pattern(pat0, 'aabc')

    pat1 = Seq('abc', min=2)
    print check_pattern(pat1, 'a')
    print check_pattern(pat1, 'ab')
    print check_pattern(pat1, 'acb')
    print check_pattern(pat1, 'abc')
    print check_pattern(pat1, 'abca')
    print check_pattern(pat1, 'aabc')

    pat2 = Seq([pat1,pat1])
    print check_pattern(pat2, 'abca')
    print check_pattern(pat2, 'abcab')
    print check_pattern(pat2, 'abab')
    print check_pattern(pat2, 'abcabc')
    print check_pattern(pat2, 'abcbbc')
    print check_pattern(pat2, 'abcXabc')

    pat3 = Pattern(items='abc', ordered=True, min_each=0, max_each=3, min_all=5)
    print check_pattern(pat3, 'abc')
    print check_pattern(pat3, 'aabbccc')
    print check_pattern(pat3, 'bbbbb')
    print check_pattern(pat3, 'aaccc')
    print check_pattern(pat3, 'accc')
    print check_pattern(pat3, 'aaabbbccc')

    pat4 = Pattern(items='abc', ordered=False, min_each=2)
    print check_pattern(pat4, 'cabbbaaabababbbba')

    pat5 = Any('abc', min=2)
    print check_pattern(pat5, 'bda')
    print check_pattern(pat5, 'b')
    print check_pattern(pat5, 'ccaa')

    pat6 = Seq( [ Choose(':;>'), Choose('-*', min=0), Choose(')/(') ] )
    print check_pattern(pat6, ':)')
    print check_pattern(pat6, ';-(')
    print check_pattern(pat6, ':*)')
    print check_pattern(pat6, '>-/')
    print check_pattern(pat6, '8-/')


# vim: ai et sw=4 ts=4
